package leetcode_500;

/**
 *@author 周杨
 *PredictTheWinner_486 做游戏 玩家1和2每次只能从数组两端选择一个数 看最后1是否比2的和大 
 *describe:用动态规划 AC 40%
 *2018年9月2日 下午6:39:57
 */
public class PredictTheWinner_486 {
	
	public static void main(String[] args) {
		PredictTheWinner_486 test=new PredictTheWinner_486();
		System.out.println(test.PredictTheWinner(new int[] {1, 5, 233, 7}));
	}
	
	 public boolean PredictTheWinner(int[] nums) {
	        if(nums.length<3)
	        	return true;
	        else
	        	return help(nums,0,nums.length-1,new int[nums.length][nums.length])>=0;
	 }
	 
	 public int help(int []nums,int l,int r,int dp[][]) {
		 if(dp[l][r]!=0)
			 return dp[l][r];
		 if(r-l==2) {//状态转移方程的结束 是3个元素的时候可以直接判断
			 if(nums[l]>nums[r]) {
				 if(nums[l+1]>nums[r])
					 return nums[l]-nums[l+1]+nums[r];
				 else
					 return nums[l]-nums[r]+nums[l+1];
			 }
			 else {
				 if(nums[l]>nums[l+1])
					 return nums[r]-nums[l]+nums[l+1];
				 else
					 return nums[r]-nums[l+1]+nums[l];
			 }
		 }
		 int res=Math.max(nums[l]-help(nums,l+1,r,dp), nums[r]-help(nums,l,r-1,dp));
		 dp[l][r]=res;
		 return res;
	 }
}
